/*
 * INSANE - Interactive Structural Analysis Environment
 *
 * Copyright (C) 2003-2005
 * Universidade Federal de Minas Gerais
 * Escola de Engenharia
 * Departamento de Engenharia de Estruturas
 * 
 * Author's email :    insane@dees.ufmg.br
 * Author's website :  http://www.dees.ufmg.br/insane
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

package br.ufmg.dees.insane.model.geo.computationalGeometry.triangulation;

import java.util.ArrayList;
import java.util.LinkedList;

import br.ufmg.dees.insane.model.geo.halfEdgeDataStructure.Edge;
import br.ufmg.dees.insane.model.geo.halfEdgeDataStructure.HalfEdgeModel;
import br.ufmg.dees.insane.model.geo.halfEdgeDataStructure.Vertex;
import br.ufmg.dees.insane.util.IPoint3d;
 
/**
 * @author Penna,S.S. & Pitangueira, Roque
 * @since 19/10/2006
 */
public class Triangulation {
	 
	public NodeD PointArray[];
	public LinkedList edgesList = new LinkedList();
	public Delaunay del;
	public HalfEdgeModel halfEdge;
	 
	/** 
	 * The constructor constructs a Delaunay triangulation from a vertices list
	 * @param vertices The vertices list
	 */
	public Triangulation(LinkedList vertices){
		this.halfEdge = new HalfEdgeModel();
		PointArray = new NodeD[vertices.size()];
		for (int i = 0; i < vertices.size(); i++){
			NodeD node = new NodeD(((Vertex)vertices.get(i)).getCoords().x,((Vertex)vertices.get(i)).getCoords().y,((Vertex)vertices.get(i)).getId());
			node.values = ((Vertex)vertices.get(i)).getValues();
			PointArray[i] = node;
		}
	}
	
	public Triangulation(){
		
	}
	
	/**
	 * The method compute the Delaunay Triangulation from this PointArray.
	 */
	public void compute(){
        for(int i=0;i<this.PointArray.length;i++){
            del.Insert(this.PointArray[i]); 
        }
	}
    
	public HalfEdgeModel fillHalfEdge(){
        HalfEdgeModel he = new HalfEdgeModel();
        //int cont = 0;
        for (int i=0; i<this.del.getTris().size(); i++){ 
            TriangleD t=(TriangleD)this.del.getTris().elementAt(i);
            LinkedList<Vertex> vertices = new LinkedList<Vertex>();
            Vertex v1 = new Vertex(t.anEdge.p1.label,new IPoint3d(t.anEdge.p1.x,t.anEdge.p1.y,0 ));
			v1.setValues(t.anEdge.p1.values);
            Vertex v2 = new Vertex(t.anEdge.getNextE().p1.label,new IPoint3d(t.anEdge.getNextE().p1.x,t.anEdge.getNextE().p1.y,0 ));
			v2.setValues(t.anEdge.getNextE().p1.values);
			Vertex v3 = new Vertex(t.anEdge.getNextE().getNextE().p1.label,new IPoint3d(t.anEdge.getNextE().getNextE().p1.x,t.anEdge.getNextE().getNextE().p1.y,0 ));
			v3.setValues(t.anEdge.getNextE().getNextE().p1.values);
			vertices.add(v1);
            vertices.add(v2);
            vertices.add(v3);
            he.fillModelFromAFace(vertices,"T"+(i+1));
        }
        he.initModel("DelaunayHalfEdgeModel");
        return he;
    }
	
//**************************************************************************************************************    
	/**
	 * The method put the Delaunay edges in a HalfEdgeModel. 
	 * @param edges The Delaunay Edges.
	 */
	public void DelaunayTrianglesToHalfEdge(LinkedList edges){
        LinkedList triangles = composeTriangles(edges);
		int cont =1;
		for (int i = 0; i < triangles.size(); i++) {
			LinkedList<Vertex> vertices = new LinkedList<Vertex>();
			Triangle t = (Triangle)triangles.get(i);
			vertices.add(t.v1);
			vertices.add(t.v2);
			vertices.add(t.v3);
			this.halfEdge.fillModelFromAFace(vertices,"T"+(i+1));
			cont++;
		}
		
	}
	
	/**
	 * The method return a list with all triangles of this DelaunayTrianguation
	 * @return A list of Delaunay Triangles
	 */
	private LinkedList composeTriangles(LinkedList edges){
		LinkedList<Triangle> triangles = new LinkedList<Triangle>();
		for (int i = 0; i < edges.size(); i++) {
			Edge e = (Edge)edges.get(i);
			Triangle t = createTriangle(e,edges);
			if(t!=null){
				if(!t.exist(triangles)){
					triangles.add(t);
				}
			}else{
				continue;
			}
		}
		return triangles;
	}
	
	/**
	 * The method create a triangle that contains a edge.
	 *  @param edges The edge list that contains the triangle's edges that will be create.
	 * @param e The edge.
	 * @return a Triangle;
	 */
	private Triangle createTriangle(Edge e,LinkedList edges){
		for(int i =0;i<edges.size();i++){
			Edge temp = (Edge)edges.get(i);
			if(!edgeEquals(temp,e)){
				if(vertexEquals(temp.getVStart(),e.getVStart())){
					Edge last = searchEdge(temp.getVEnd(),e.getVEnd(),temp,e);
					if(last!=null){
						return new Triangle(temp,e,last);
					}
				}
				if(vertexEquals(temp.getVStart(),e.getVEnd())){
					Edge last = searchEdge(temp.getVEnd(),e.getVStart(),temp,e);
					if(last!=null){
						return new Triangle(temp,e,last);
					}
				}
				if(vertexEquals(temp.getVEnd(),e.getVEnd())){
					Edge last = searchEdge(temp.getVStart(),e.getVStart(),temp,e);
					if(last!=null){
						return new Triangle(temp,e,last);
					}
				}
				if(vertexEquals(temp.getVEnd(),e.getVStart())){
					Edge last = searchEdge(temp.getVStart(),e.getVEnd(),temp,e);
					if(last!=null){
						return new Triangle(temp,e,last);
					}
				}
			}else{
				continue;
			}
		}
		return null;
	}
	
	/**
	 *  The method search a edge composed by two vertex passed by parameter
	 * @param v1 The vertex one.
	 * @param v2 The vertex two.
	 * @return a edge
	 */
	private Edge searchEdge(Vertex v1, Vertex v2,Edge e1,Edge e2){
		for(int i =0;i<edgesList.size();i++){
			Edge temp = (Edge)edgesList.get(i);
			if(!edgeEquals(temp,e1)&&!edgeEquals(temp,e2)){
				if(vertexEquals(temp.getVStart(),v1)&&vertexEquals(temp.getVStart(),v2)
						   ||vertexEquals(temp.getVEnd(),v1)&&vertexEquals(temp.getVStart(),v2)){
					return temp;
				}else{
					continue;
				}
			}
			
		}
		return null;
	}
	
	/**
	 * The method return a triangle composed by two edges passed by parameter
	 * @param e1 The edge one.
	 * @param e2 The edge two.
	 * @return a triangle
	 */
	@SuppressWarnings("unused")
	private Triangle searchTriangleByEdges(Edge e1,Edge e2){
		for(int i =0;i<edgesList.size();i++){
			Edge temp = (Edge)edgesList.get(i);
			if(!temp.equals(e1)&&!temp.equals(e2)){
				if(  vertexEquals(temp.getVStart(),e1.getVStart())&&vertexEquals(temp.getVEnd(),e2.getVStart())
				   ||vertexEquals(temp.getVStart(),e1.getVEnd())&&vertexEquals(temp.getVEnd(),e2.getVEnd())
				   ||vertexEquals(temp.getVStart(),e1.getVStart())&&vertexEquals(temp.getVEnd(),e2.getVEnd())
				   ||vertexEquals(temp.getVStart(),e1.getVEnd())&&vertexEquals(temp.getVEnd(),e2.getVStart())){
					return new Triangle(e1,e2,temp);
				}
			}else{
					continue;
			}
		}
		return null;
	}
	
	/**
	 * The method compare two vertices by their coords. 
	 * @param v1 The vertex one.
	 * @param v2 The vertex two
	 * @return true if the coords are equals and return false if the coords are diferets.
	 */
	private boolean vertexEquals(Vertex v1, Vertex v2){
        if(((IPoint3d)v1.getCoords()).distance(v2.getCoords())<=0.001){
            return true;
        }else{
            return false;
        }
	}
	
	/**
	 * The method compare two edges by their coords. 
	 * @param e1 The edge one.
	 * @param e2 The edge two.
	 * @return true if the coords are equals and return false if the coords are diferets.
	 */
	private boolean edgeEquals(Edge e1, Edge e2){
		if(vertexEquals(e1.getVStart(),e2.getVStart())&& vertexEquals(e1.getVEnd(),e2.getVEnd())
				||vertexEquals(e1.getVEnd(),e2.getVStart())&& vertexEquals(e1.getVStart(),e2.getVEnd())){
			return true;
		}else {
			return false;

		}
	}
	
//**************************************************************************************
}//end of this class

/**
 * This internal class represents a Delaunay triangle.
 * @author Penna, S.S. & Pitangueira, Roque
 * @since 19/10/2006
 */
class Triangle{
    
	public Vertex v1;
    public Vertex v2;
    public Vertex v3;
    public Edge e1;
    public Edge e2;
    public Edge e3;

    /** 
     * The constructor constructs a triangle by three edges
     * @param e1 The edge one.
     * @param e2 The edge two.
     * @param e3 The edge three.
     */
    public Triangle(Edge e1,Edge e2,Edge e3){ 
    	this.e1=e1;
    	this.e2=e2;
    	this.e3=e3;
    	this.initVertex();
    }
    
    /**
     * The method initialize the vertices of triangle
     */
    private void initVertex(){
    	ArrayList<Vertex> vertices = new ArrayList<Vertex>();
    	vertices.add(e1.getVStart());
    	vertices.add(e1.getVEnd());
    	if(!vertexEquals(e1.getVStart(),e2.getVStart())&&!vertexEquals(e1.getVEnd(),e2.getVStart())){
    		vertices.add(e2.getVStart());
    	}
    	if(!vertexEquals(e1.getVStart(),e2.getVEnd())&&!vertexEquals(e1.getVEnd(),e2.getVEnd())){
    		vertices.add(e2.getVEnd());
    	}
    	this.v1 = (Vertex)vertices.get(0);
    	this.v2 = (Vertex)vertices.get(1);
    	this.v3 = (Vertex)vertices.get(2); 
    }
    
    /**
     * The method check if a triangle list contains this triangle 
     * @param triangles The triangle list. 
     * @return true if The list contains the triangle or false if don't.
     */
    public boolean exist(LinkedList triangles){
    	for (int i = 0; i < triangles.size(); i++) {
			Triangle t = (Triangle)triangles.get(i);
			if(this.triangleEquals(t)){
				return true;
			}
		}
    	return false;
    }
    
    /**
	 * The method compare this triangle with a triangle passaded by parameter.
	 * This method use the vertices of both triangles to make the comparison. 
	 * @param t The triangle.
	 * @return true if the triangles are equals and return false if the triangles are diferets.
	 */
    private boolean triangleEquals(Triangle t){
    	if(vertexEquals(this.v1,t.v1)&&vertexEquals(this.v2,t.v2)&&vertexEquals(this.v3,t.v3)){
			return true;
		}
    	if(vertexEquals(this.v1,t.v1)&&vertexEquals(this.v2,t.v3)&&vertexEquals(this.v3,t.v2)){
			return true;
		}
		if(vertexEquals(this.v1,t.v2)&&vertexEquals(this.v2,t.v1)&&vertexEquals(this.v3,t.v3)){
			return true;
		}
		if(vertexEquals(this.v1,t.v2)&&vertexEquals(this.v2,t.v3)&&vertexEquals(this.v3,t.v1)){
			return true;
		}
		if(vertexEquals(this.v1,t.v3)&&vertexEquals(this.v2,t.v1)&&vertexEquals(this.v3,t.v2)){
			return true;
		}
		if(vertexEquals(this.v1,t.v3)&&vertexEquals(this.v2,t.v2)&&vertexEquals(this.v3,t.v1)){
			return true;
		}
		return false;
	}
    
    /**
	 * The method compare two vertices by their coords. 
	 * @param v1 The vertex one.
	 * @param v2 The vertex two
	 * @return true if the coords are equals and return false if the coords are diferets.
	 */
    private boolean vertexEquals(Vertex v1, Vertex v2){
        
        if(((IPoint3d)v1.getCoords()).distance(v2.getCoords())<=0.001){
            return true;
        }else{
            return false;
        }
	}
    
//********************************************************************************************    
}//end of this internal class
 
